package com.ifreeee.sort;

import org.junit.Test;

import java.util.Arrays;
import java.util.Random;

public class InsertionSort {

    /**
     * 插入排序
     * @param arr
     */
    public static void insertionSort(int[] arr){
        insertionSort(arr, 0, arr.length - 1);
    }

    /**
     * 数组的某个闭区间 [lIndex, rIndex] 内，插入排序 使之有序
     * @param arr 数组
     * @param lIndex
     * @param rIndex
     */
    public static void insertionSort(int[] arr, int lIndex, int rIndex){
        int i = lIndex + 1 , j, len = rIndex + 1, temp;
        for( ; i < len; i += 1){
            temp = arr[i];
            for(j = i; j > 0; j -= 1){
                if(temp < arr[j - 1]){
                    arr[j] = arr[j - 1];
                }else{
                    break;
                }
            }
            arr[j] = temp;
        }
    }

    @Test
    public void test1(){
        int len = 40;
        int[] arr = new int[len];
        Random r = new Random();//随机数对象
        for(int i = 0; i < len; i += 1){
            arr[i]  =  r.nextInt(len);
        }
        InsertionSort.insertionSort(arr/*, 25, 38*/);
        System.out.println(Arrays.toString(arr));
    }

}
